package medium

import "sort"

/*
时间复杂度:O(N)
空间复杂度:O(N)

关键点: 只有池塘A在第i天已经有水,且在第i天之后有天晴的日子,等到A再次下雨的时候,才可以借助之前天晴的日子先对A进行排水,这样再次下雨时A就不会溢出
解决:通过slice存储所有晴天的索引,然后每次一个池塘在已经有水的情况下再次下雨,则判断是否存在比该池塘前一次有水时的索引要大的晴天
*/

func avoidFlood(rains []int) []int {
	// 存储已经有水的池塘编号及其索引
	hash := make(map[int]int)
	// 存储晴天的索引
	sunny := make([]int, 0)
	// 存储最终结果
	result := make([]int, len(rains))
	for i, v := range rains {
		if v == 0 {
			// 先通过1占位(因为如果没有需要抽干的池塘,则晴天必须指定一个任意需要抽干的池塘)
			result[i] = 1
			sunny = append(sunny, i)
			continue
		}
		if last, ok := hash[v]; ok {
			// 找到在已有水的池塘之后的第一个晴天
			idx := sort.Search(len(sunny), func(i int) bool {
				return sunny[i] > last
			})
			if idx == len(sunny) {
				return []int{}
			}
			result[sunny[idx]] = v
			// 这个晴天用来抽了v池塘的水,不能再使用
			sunny = append(sunny[:idx], sunny[idx+1:]...)
		}
		result[i] = -1
		// 记录池塘v新的索引
		hash[v] = i
	}
	return result
}
